package dfs_bfs.test473;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * 火柴拼正方形
 * @author code_yc
 * @version 1.0
 * @date 2020/7/9 12:41
 */
public class Solution1 {


    boolean[] f;
    int n;

    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) return false;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 4 != 0) return false;
        n = nums.length;
        f = new boolean[n];
        Arrays.sort(nums);
        return dfs(nums, 0, 0, sum / 4);
    }

    private boolean dfs(int[] nums, int u, int cur, int len) {
        if (cur == len) {
            u++;
            cur = 0;
        }
        if (u == 4) return true;
        for (int i = n - 1; i >= 0; i--) {
            if (!f[i] && cur + nums[i] <= len) {
                f[i] = true;
                if (dfs(nums, u, cur + nums[i], len)) return true;
                f[i] = false;
                // 如果第一元素加上如不满足的话，或者最后一个元素加上去不满足的话，直接返回false
                if (cur == 0 || cur + nums[i] == len) return false;
                while (i - 1 >= 0 && nums[i - 1] == nums[i]) i--;    // 相同的元素也进行剪枝
            }
        }
        return false;
    }
}
